\documentclass[]{article}
\usepackage{xeCJK}
\setCJKmainfont{Noto Serif CJK TC}
\usepackage[a4paper]{geometry}
\usepackage{setspace}
\usepackage{amsmath} 
\onehalfspacing
\usepackage{float}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\begin{center}
\Huge \textbf{数值分析第二次理论作业} \\ [0.2cm]
\LARGE 林敬翊 3210300367 信息与计算科学

\end{center}

\section{Q I}
解：可知$f(x)=\frac{1}{x}, x_{0}=1, x_{1}=2$.运用拉格朗日公式可得：
$$
p_1(f;x) = 1\times \frac{x - 2}{1 - 2} + \frac{1}{2}\times\frac{x - 1}{2 - 1} = -\frac{1}{2}x + \frac{3}{2}
$$
由题目
$$
f(x)-p_{1}(f ; x)=\frac{f^{\prime \prime}(\xi(x))}{2}\left(x-x_{0}\right)\left(x-x_{1}\right) .
$$
代入后得到
$$\frac{1}{x} + \frac{1}{2}x - \frac{3}{2} = \frac{1}{\xi^3(x)(x - 1)(x - 2)} $$
经过整理可得
$$\xi(x) = \sqrt[3]{2x} $$
将$x_0$和$x_1$代入可得最大和最小
$$max\xi(x) = \xi(2) = \sqrt[3]{4}, min\xi(x) = \xi(1) = \sqrt[3]{2}$$
因为$f''(\xi(x))=\frac{2}{\xi^3(x)}=\frac{1}{x} $，所以
$$maxf''(\xi(x)) = 1 $$
\section{Q II}
解：利用拉格朗日插值公式，我们可以找到一个多项式$q(x)\in P_n$满足
$$q(x_i) = \sqrt{f_i}, \qquad i = 0,1,...,n $$
在根据Definition 2.10，可得
$$q(x) = \sum_{i=0}^n (\sqrt{f_i}\prod \limits_{ i\neq k ,i=0}^n \frac{x - x_i}{x_k - x_i})$$
令$p(x) = q^2(x)$, 则$p(x)\in P_{2n}^+$, 且对任意$i = 0,1,...,n$
有
$$p(x) = \Bigl(\sum_{i=0}^n (\sqrt{f_i}\prod \limits_{ i\neq k ,i=0}^n \frac{x - x_i}{x_k - x_i})\Bigr)^2 $$
\section{Q III}
解：首先，我们使用数学归纳法证明给定的等式。对于任意实数\(t\)，定义函数\(f(x) = e^{x}\)。我们想要证明对于所有非负整数\(n\)，都有：

\[
f[t, t+1, \ldots, t+n] = \frac{(e-1)^{n}}{n!} e^{t}.
\]

\textbf{基础情形：} 当\(n = 0\) 时，我们有\(f[t] = e^{t}\)，符合等式左边。同时，等式右边为\(\frac{(e-1)^{0}}{0!} e^{t} = e^{t}\)，两边相等。

\textbf{归纳假设：} 假设对于某个非负整数\(k\)，等式对\(n = k\) 成立，即：

\[
f[t, t+1, \ldots, t+k] = \frac{(e-1)^{k}}{k!} e^{t}.
\]

\textbf{归纳步骤：} 考虑\(n = k + 1\) 的情况。我们有：

$$
f[t, t+1, \ldots, t+k, t+k+1] 
$$
$$= f[t, t+1, \ldots, t+k] \times f[t+k+1]$$
$$ = \frac{(e-1)^{k}}{k!} e^{t} \times e^{t+k+1} $$
$$ = \frac{(e-1)^{k} e^{t+k+1}}{k!} $$
$$ = \frac{(e-1)^{k+1}}{(k+1)!} e^{t}.$$


所以，由数学归纳法可知，对于所有非负整数\(n\)，等式都成立。

接下来，我们知道存在\(\xi \in(0, n)\)，使得：

\[
f[0,1, \ldots, n] = \frac{1}{n!} f^{(n)}(\xi).
\]

结合第一个等式，我们有：

\[
\frac{(e-1)^{n}}{n!} e^{0} = \frac{1}{n!} f^{(n)}(\xi).
\]

化简得：

\[
(e-1)^{n} = f^{(n)}(\xi).
\]

我们无法精确确定\(\xi\) 的值，但我们知道它位于\(0\) 和 \(n\) 之间。对于\(\xi\) 与\(\frac{n}{2}\) 的相对位置，我们无法直接得出，除非我们知道\(n\) 的具体值。但是，我们可以说\(\xi\) 在中点\(\frac{n}{2}\) 的左侧或右侧，具体取决于\(n\) 的值。

\section{Q IV}
经过差分法可知：
\begin{table}[H]
	\centering
	\begin{tabular}{l|llll}
		 0 & 5  &    &   &  \\
		 1 & 3  & -2 &   &  \\
		 3 & 5  & 1  & 1 &  \\
		 4 & 12 & 7  & 2 & 0.25 \\
	\end{tabular}
\end{table}
使用牛顿差值公式可得
$$
p_3(f;x) = 5 -2x + x(x - 1) + \frac{1}{4}x(x - 1)(x - 3) = \frac{1}{4}x^3 - \frac{9}{4}x + 5 
$$
微分得
$$p'_3(f;x) = \frac{3}{4}x^2 - \frac{9}{4}$$
$$
p'_3(f;x)\ge0 \Rightarrow x\ge\sqrt{3}
$$
所以
$x_{min} = \sqrt{3}$
\section{Q V}
差分表如下:
\begin{table}[H]
	\centering
	\begin{tabular}{l|llllll}
		 0 & 0   &     &     &     &     &    \\
		 1 & 1   & 1   &     &     &     &    \\
		 1 & 1   & 7   & 6   &     &     &    \\
		 1 & 1   & 7   & 21  & 15  &     &    \\
		 2 & 128 & 127 & 120 & 99  & 42  &    \\
		 2 & 128 & 448 & 321 & 201 & 102 & 30
	\end{tabular}
\end{table}
所以可知$f[0,1,1,1,2,2]=30$
$$f[0,1,1,1,2,2]=\frac{f^{(5)}(\xi)}{5!}=30,\xi \in (0,2) \Rightarrow \xi= \frac{\sqrt{70}}{7} \in (0,2)$$
\section{Q VI}
\begin{table}[H]
	\centering
	\begin{tabular}{l|lllll}
		 0 & 1 &    &     		  	 &    &    \\
		 1 & 2 & 1  &    			 &    &    \\
		 1 & 2 & -1 & -2 			 &    &    \\
		 3 & 0 & -1 & 0  			 & $\frac{2}{3}$ &    \\
		 3 & 0 & 0  & $\frac{1}{2}$ & $\frac{1}{4}$ & $-\frac{5}{36}$
	\end{tabular}
\end{table}
根据牛顿差值公式可得
$$
p_4(f;x) = 1 + x - 2x(x -1) + \frac{2}{3}x(x - 1)(x - 1) - \frac{5}{36}x(x - 1)(x - 1)(x - 3) 
$$
$$
= -\frac{5}{36}x^4 + \frac{49}{36}x^3 - \frac{155}{36}x^2 + {12}x + 1 
$$
所以有$f(2) \approx p_4(f;2) = \frac{11}{18}$\\
再有$$f(x) - p_4(f;x) = \frac{f^{(5)}(\xi)}{120}x(x - 1)^2(x - 3)^2 $$
从而
$$|f(2) - p_4(f;x)| = |\frac{f^{(5)}(\xi)}{120}2(2 - 1)^2(2 - 3)^2| \leq \frac{M}{60} $$
\section{Q VII}
刚开始我们有$k=1, \Delta f(x)=f(x_1)-f(x_0)=hf[x_0,x_1]$,

当 $n=k$, 我们有

\[\Delta^k f(x)=k!h^k f[x_0,x_1,\ldots, x_k]\]

当$n=k+1$,
\[\Delta^{k+1} f(x)=\Delta^k f(x+h)-\Delta^k(x)\]
\[=k!h^k f[x_1,\ldots,x_{k+1}]-k!h^k f[x_0,\ldots,x_k]=(k+1)!h^{k+1} f[x_0,\ldots,x_{k+1}]\]

相似的当 $k=1, \nabla  f(x)=f(x_0)-f(x_{-1})=hf[x_0,x_{-1}]$,

当 $n=k$, 我们有

\[\nabla^k f(x)=k!h^k f[x_0,x_{-1},\ldots, x_{-k}]\]

当 $n=k+1$,我们有
\[\nabla^{k+1} f(x)=\nabla^k f(x)-\nabla^k(x-h)\]
\[=k!h^k f[x_0,\ldots,x_{-k}]-k!h^k f[x_{-1},\ldots,x_{-k-1}]=(k+1)!h^{k+1} f[x_0,\ldots,x_{-(k+1)}]\]
\section{Q VIII}
证明
\[
\frac{\partial}{\partial x_0} f[x_0, x_1, \ldots, x_n] = f[x_0, x_0, x_1, \ldots, x_n].
\]

偏导数的定义是
\[
\frac{\partial}{\partial x_0} f[x_0, x_1, \ldots, x_n] = \lim_{{h \to 0}} \frac{f[x_0 + h, x_1, \ldots, x_n] - f[x_0, x_1, \ldots, x_n]}{h}.
\]

计算 $f[x_0 + h, x_1, \ldots, x_n]$
\[
f[x_0 + h, x_1, \ldots, x_n] = \sum_{k=0}^n \left( f(x_k) \prod_{{j=0, j\neq k}}^n \frac{h + x_0 - x_j}{x_k - x_j} \right).
\]
计算偏导数
\begin{align*}
\frac{\partial}{\partial x_0} f[x_0, x_1, \ldots, x_n] &= \lim_{h \to 0} \frac{\sum_{k=0}^n \left( f(x_k) \prod_{j=0, j\neq k}^n \frac{h + x_0 - x_j}{x_k - x_j} \right) - \sum_{k=0}^n \left( f(x_k) \prod_{j=0, j\neq k}^n \frac{x_0 - x_j}{x_k - x_j} \right)}{h} \
\end{align*}
$$
= \lim_{h \to 0} \sum_{k=0}^n \left( f(x_k) \prod_{j=0, j\neq k}^n \frac{\frac{h + x_0 - x_j}{x_k - x_j} - \frac{x_0 - x_j}{x_k - x_j}}{h} \right) 
$$

$$
= \lim_{h \to 0} \sum_{k=0}^n \left( f(x_k) \prod_{j=0, j\neq k}^n \frac{h}{h(x_k - x_j)} \right) 
$$

$$
= \sum_{k=0}^n \left( f(x_k) \prod_{j=0, j\neq k}^n \frac{1}{(x_k - x_j)} \right) \
$$

$$
= f[x_0, x_0, x_1, \ldots, x_n].
$$
\section{Q IX}
根据Corollary 2.45
$$\min \max_{x \in [-1,1]}|x^n+a_1x^{n-1}+\cdots+a_n|=\frac{1}{2^{n-1}}$$
做线性变换可得
$$x=\frac{b-a}{2}t+\frac{a+b}{2},t \in [-1,1], x \in [a,b]$$
解得
$$\min \max_{x \in [a,b]}|x^n+a_1x^{n-1}+\cdots+a_n|= \min \max_{t \in [-1,1]} |a_0\left(\frac{b-a}{2}t+\frac{a+b}{2}\right)^n+\cdots| $$
$$=a_0\left(\frac{b-a}{2}\right)^n\frac{1}{2^{n-1}}$$
$$=\frac{a_0(b-a)^n}{2^{2n-1}}$$
\section{Q X}
定义多项式$\hat{p}_n(x)$为：

\[ \hat{p}_n(x) = \frac{\hat{T}_n(t)}{\hat{T}_n(\ln(a))}, \quad x = \cosh(t). \]

现在我们来证明对于任意$p \in \mathbb{P}_n^a$，都有$\|\hat{p}_n\|_\infty \leq \|p\|_\infty$。

首先，$\hat{T}_n(t)$的最高次项系数是$2^{n-1}$，所以$\hat{T}_n(\ln(a))$的绝对值是$2^{n-1}$。因此，$\|\hat{p}_n\|_\infty$可以写成：

\[ \|\hat{p}_n\|_\infty = \max_{x \in [1, \infty)} \left| \frac{\hat{T}_n(\ln(\cosh^{-1}(x)))}{2^{n-1}} \right|. \]

考虑$\ln(\cosh^{-1}(x))$，其中$x \in [1, \infty)$。$\cosh^{-1}(x) = \ln(x + \sqrt{x^2 - 1})$，所以：

\[ \ln(\cosh^{-1}(x)) = \ln(x + \sqrt{x^2 - 1}). \]

证明：

\[ \max_{x \in [1, \infty)} \left| \frac{\hat{T}_n(\ln(x + \sqrt{x^2 - 1}))}{2^{n-1}} \right| \leq \max_{x \in [1, a]} |p(x)|. \]

由于$\hat{T}_n(\ln(x + \sqrt{x^2 - 1}))$是$\hat{p}_n(x)$的分子部分，只需要证明$\left| \frac{1}{2^{n-1}} \right| \leq \max_{x \in [1, a]} |p(x)|$。这是因为$\hat{p}_n(x)$的分母部分是$\hat{T}_n(\ln(a))$，它的绝对值是$2^{n-1}$。

因此，只需要证明对于所有$p \in \mathbb{P}_n^a$，有$|p(x)| \geq 1$ 对于$x \in [1, a]$。这是因为$p(a) = 1$，并且$p(x)$是一个次数不超过$n$的多项式。由Chebyshev polynomial的性质可知，它在$[-1, 1]$上的绝对值至少为$1$，所以在$[1, a]$上的绝对值也至少为$1$。

综上所述，对于任意$p \in \mathbb{P}_n^a$，有$\|\hat{p}_n\|_\infty \leq \|p\|_\infty$，证毕。

\section{Q XI}
证明
$$
\begin{aligned}
\forall k=0,1, \ldots, n, \forall t \in(0,1), \quad b_{n, k}(t) & >0 -----(1)\\
\sum_{k=0}^{n} b_{n, k}(t) & =1,-----(2) \\
\sum_{k=0}^{n} k b_{n, k}(t) & =n t -----(3)\\
\sum_{k=0}^{n}(k-n t)^{2} b_{n, k}(t) & =n t(1-t)  . -----(4)
\end{aligned}
$$
证明（1），由于是一个二项式系数，所以里面的元素一定都$>0$\\
证明（2）,
$$
\sum_{k=0}^{n} b_{n, k}(t) = \sum_{k=0}^{n} \binom{n}{k} t^k (1-t)^{n-k} = (t + (1-t))^n = 1
$$
证明（3），
$$
\sum_{k=0}^{n} k b_{n, k}(t) &= \sum_{k=0}^{n} k \binom{n}{k} t^k (1-t)^{n-k} 
$$

$$
= n\sum_{k=1}^{n} \binom{n-1}{k-1} t^k (1-t)^{n-k}
$$
$$= nt\sum_{k=1}^{n} \binom{n-1}{k-1} t^{k-1} (1-t)^{(n-1)-(k-1)} $$
$$= nt(t + (1-t))^{n-1}$$
$$= nt$$
证明（4），
\begin{align}
\sum_{k=0}^n k^2b_{n,k}(t) &= \sum_{k=0}^n k^2\tbinom{n}{k}t^k(1-t)^{n-k} \notag \\
&= n(n-1)\sum_{k=2}^n\tbinom{n-2}{k-2}t^k(1-t)^{n-k} + n\sum_{k=1}^n\tbinom{n-1}{k-1}t^k(1-t)^{n-k} \notag \\
&= n(n-1)t^2\sum_{k=0}^{n-2}\tbinom{n-2}{k}t^k(1-t)^{n-2-k} + nt\sum_{k=0}^{n-1}\tbinom{n-1}{k}t^k(1-t)^{n-1-k}\notag \\
&= n(n-1)t^2[t+(1-t)]^{n-2} + nt[t+(1-t)]^{n-1}\notag \\
&= n(n-1)t^2 + nt \notag
\end{align}
\begin{align}
\sum_{k=0}^n (k-nt)^2b_{n,k}(t) &= \sum_{k=0}^n k^2b_{n,k}(t) - 2nt\sum_{k=0}^{n}kb_{n,k}(t) + n^2t^2\sum_{k=0}^{n}b_{n,k}(t) \notag \\
&= n(n-1)t^2 + nt -2n^2t^2 + n^2t^2 \notag \\
&= nt(1-t)\notag 
\end{align}
\end{document}